{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree(object):#括号里是继承的父类#\n",
    "    #树#\n",
    "    class Position(object):\n",
    "        def element(self):\n",
    "            raise NotImplementedError('must implemented by subclass')\n",
    "            \n",
    "        def __eq__(self,other):#==被__eq__重载#\n",
    "            raise NotImplementedError('must implemented by subclass')\n",
    "            \n",
    "        def __neq__(self,other):#~=被__neq__重载#\n",
    "            return not (self==other)\n",
    "    \n",
    "    def root(self):\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "        \n",
    "    def parent(self,p):#找父节点#\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "    \n",
    "    def num_children(self,p):#找孩子节点数量#\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "    \n",
    "    def children(self,p):#找孩子节点#\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "        \n",
    "    def positions(self):\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "    \n",
    "    def __len__(self):#节点总数#\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "        \n",
    "    def is_root(self,p):\n",
    "        return p == self.root()\n",
    "    \n",
    "    def is_leaf(self,p):\n",
    "        return self.num_children(p) == 0\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self) == 0\n",
    "    \n",
    "    def depth(self,p):\n",
    "        if self.is_root():\n",
    "            return 0\n",
    "        else:\n",
    "            return self.depth(self.parent(p)) + 1\n",
    "    \n",
    "    def _height(self,p):\n",
    "        if self.is_leaf():\n",
    "            return 0\n",
    "        else:\n",
    "            return max([self._height(c) for c in self.children(p)]) + 1\n",
    "            #max方法对list进行操作，应该用列表生成式写递归#\n",
    "    \n",
    "    def height(self,p=None):\n",
    "        if p==None:\n",
    "            p=self.root()\n",
    "        return self._height(p)\n",
    "    \n",
    "    def height1(self):#树的高度，时间复杂度O(n^2)#\n",
    "        return max([self.depth(p) for p in self.positions() if self.is_leaf(p)])\n",
    "    \n",
    "    def _preorder(self):\n",
    "        #前序遍历#\n",
    "        if not self.is_empty():\n",
    "            for p in self._subtree_preoder(self.root()):\n",
    "                yield p\n",
    "    def _subtree_preoder(self,p):\n",
    "        #对子树的前序遍历#\n",
    "        \"\"\"Generate a preorder iteration of positions in subtree rooted at p.\"\"\"\n",
    "        yield p\n",
    "        for c in self.children(p):\n",
    "            for other in self._subtree_preoder(c):\n",
    "                yield other\n",
    "                \n",
    "    def _postorder(self):\n",
    "        if not self.is_empty():\n",
    "            for p in self._subtree_postorder(self.root()):\n",
    "                yield p    \n",
    "    def _subtree_postorder(self,p):\n",
    "        for c in self.children(p):\n",
    "            for other in self._subtree_postorder(c):\n",
    "                yield other\n",
    "        yield p\n",
    "        \n",
    "    def breadthfirst(self):\n",
    "        #广度优先遍历#\n",
    "        #没有用到递归，任何队列ADT都可以#\n",
    "        if not self.is_empty():\n",
    "            Q=LinkedQueue()\n",
    "            Q.enqueue(self.root())\n",
    "            while not Q.is_empty():\n",
    "                p=Q.dequeue()\n",
    "                yield p\n",
    "                for c in self.children(p):\n",
    "                    Q.enqueue(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedQueue(object):\n",
    "    class _Node(object):\n",
    "        def __init__(self,element,next):\n",
    "            self._element=element\n",
    "            self._next=next\n",
    "            \n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._tail = None\n",
    "        self._size = 0\n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty')\n",
    "        return self._head._element\n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty')\n",
    "        result = self._head._element\n",
    "        self._head=self._head._next\n",
    "        self._size -=1\n",
    "        if self.is_empty():\n",
    "            self._tail = None\n",
    "        return result\n",
    "    def enqueue(self,e):\n",
    "        node = self._Node(e,None)\n",
    "        if self.is_empty():\n",
    "            self._head= node\n",
    "        else:    \n",
    "            self._tail._next=node\n",
    "        self._tail=node\n",
    "        self._size+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree(Tree):\n",
    "    #二叉树#\n",
    "    #抽象基类没有init方法#\n",
    "    def left(self,p):\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "    \n",
    "    def right(self,p):\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "    \n",
    "    def sibling(self,p):#返回兄弟节点的位置#\n",
    "        parent = self.parent(p)\n",
    "        if parent is None:\n",
    "            return None\n",
    "        else:\n",
    "            if p ==self.left(parent):\n",
    "                return self.right(parent)\n",
    "            else:\n",
    "                return self.left(parent)\n",
    "            \n",
    "    def children(self,p):\n",
    "        if self.left(p) is not None: \n",
    "            yield self.left(p) \n",
    "        if self.right(p) is not None: \n",
    "            yield self.right(p)\n",
    "            \n",
    "    def _inorder(self):\n",
    "        #中序遍历#\n",
    "        if not self.is_empty():\n",
    "            for p in self._subtree_inorder(self.root()):\n",
    "                yield p\n",
    "    \n",
    "    def _subtree_inorder(self,p):\n",
    "        if self.left(p) is not None:\n",
    "            for other in self._subtree_inorder(self.left(p)):\n",
    "                yield other\n",
    "        yield p #子树的根节点#\n",
    "        if self.right(p) is not None:\n",
    "            for other in self._subtree_inorder(self.right(p)):\n",
    "                yield other"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedBinaryTree(BinaryTree):\n",
    "    #二叉树的链式结构实现#\n",
    "    class _Node(object):\n",
    "        __slots__='_elem','_parent','_left','_right'\n",
    "        def __init__(self,elem,parent=None,left=None,right=None):\n",
    "            self._elem=elem\n",
    "            self._parent=parent\n",
    "            self._left=left\n",
    "            self._right=right\n",
    "    class Position(BinaryTree.Position):\n",
    "        def __init__(self,container,node):\n",
    "            self._container=container\n",
    "            self._node=node\n",
    "        \n",
    "        def elem(self):\n",
    "            return self._node._elem\n",
    "        \n",
    "        def __eq__(self,other):\n",
    "            return type(self) is type(other) and self._node is other._node\n",
    "        \n",
    "    def __init__(self):\n",
    "        self._root=None\n",
    "        self._size=0\n",
    "    \n",
    "    def _validate(self,p):\n",
    "        if not isinstance(p,self.Position):\n",
    "            raise TypeError('p must be a proper Position')\n",
    "        if p._container is not self:\n",
    "            raise ValueError('p does not belong to this tree')\n",
    "        if p._node._parent is p._node:\n",
    "            raise ValueError('p is no longer valid')\n",
    "        return p._node\n",
    "    \n",
    "    def _make_position(self,node):\n",
    "        return self.Position(self,node) if node is not None else None\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def root(self):\n",
    "        return self._make_position(self._root)\n",
    "    \n",
    "    def parent(self,p):\n",
    "        node=self._validate(p)\n",
    "        return self._make_position(node._parent)\n",
    "    \n",
    "    def left(self,p):\n",
    "        node=self._validate(p)\n",
    "        return self._make_position(node._left)\n",
    "    \n",
    "    def right(self,p):\n",
    "        node=self._validate(p)\n",
    "        return self._make_position(node._right)\n",
    "    \n",
    "    def num_children(self,p):\n",
    "        node=self._validate(p)\n",
    "        count=0\n",
    "        if node._left is not None:\n",
    "            count +=1\n",
    "        if node._right is not None:\n",
    "            count +=1\n",
    "        return count\n",
    "    \n",
    "    def add_root(self,e):\n",
    "        if not self.is_empty():\n",
    "            raise ValueError('Root exists')\n",
    "        self._size+=1\n",
    "        self._root=self._Node(e)\n",
    "        return self._make_position(self._root)\n",
    "    \n",
    "    def add_left(self,p,e):\n",
    "        node=self._validate(p)\n",
    "        if node._left is not None:\n",
    "            raise ValueError('Left child exists')\n",
    "        self._size+=1\n",
    "        node._left = self._Node(e)\n",
    "        return self._make_position(node._left)\n",
    "    \n",
    "    def add_right(self,p,e):\n",
    "        node=self._validate(p)\n",
    "        if node._right is not None:\n",
    "            raise ValueError('Right child exists')\n",
    "        self._size+=1\n",
    "        node._right = self._Node(e)\n",
    "        return self._make_position(node._right)\n",
    "    \n",
    "    def replace(self,p,e):\n",
    "        node=self._validate(p)\n",
    "        old=node._elem\n",
    "        node._elem=e\n",
    "        return old\n",
    "    \n",
    "    def delete(self,p):\n",
    "        if self.num_children(p)==2:\n",
    "            raise ValueError('p has two children')\n",
    "        node =self._validate(p)\n",
    "        child =node._left if node._left else node._right\n",
    "        \n",
    "        if child is not None:\n",
    "            child._parent=node._parent\n",
    "        if node is self._root:\n",
    "            self._root=child\n",
    "        else:\n",
    "            parent = node._parent\n",
    "            if node is parent._left:\n",
    "                parent._left = child\n",
    "        \n",
    "        self._size -=1\n",
    "        node._parent=node\n",
    "        return node._elem\n",
    "    \n",
    "    def _attach(self,p,t1,t2):\n",
    "        node=self._validate(p)\n",
    "        if not self.is_leaf(p):raise ValueError('position must be leaf')\n",
    "        if not type(self) is type(t1) is type(t2):\n",
    "            raise TypeError('Tree type must match')\n",
    "        self._size+=len(t1)+len(t2)\n",
    "        if not t1.is_empty():\n",
    "            t1._root._parent=node\n",
    "            node._left=t1._root\n",
    "            t1._root=None\n",
    "            t1._size=0\n",
    "        if not t2.is_empty():\n",
    "            t2._root._parent=node\n",
    "            node._right=t2._root\n",
    "            t2._root=None\n",
    "            t2._size=0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.LinkedBinaryTree.Position object at 0x0000027D61DD2358>\n",
      "results_preorder:['a', 'b', 'd', 'e', 'f', 'g', 'c']\n",
      "results_postorder:['d', 'f', 'g', 'e', 'b', 'c', 'a']\n",
      "results_inorder:['d', 'b', 'f', 'e', 'g', 'a', 'c']\n",
      "results_breadthfirst:['a', 'b', 'c', 'd', 'e', 'f', 'g']\n"
     ]
    }
   ],
   "source": [
    "T=LinkedBinaryTree()#初始化#\n",
    "a=T.add_root('a')\n",
    "print(a)\n",
    "b=T.add_left(a,'b')\n",
    "c=T.add_right(a,'c')\n",
    "\n",
    "d=T.add_left(b,'d')\n",
    "e=T.add_right(b,'e')\n",
    "\n",
    "f=T.add_left(e,'f')\n",
    "g=T.add_right(e,'g')\n",
    "\n",
    "results_preorder = [p.elem() for p in T._preorder()]\n",
    "print(f'results_preorder:{results_preorder}')\n",
    "\n",
    "results_postorder = [p.elem() for p in T._postorder()]\n",
    "print(f'results_postorder:{results_postorder}')\n",
    "\n",
    "results_inorder = [p.elem() for p in T._inorder()]\n",
    "print(f'results_inorder:{results_inorder}')\n",
    "\n",
    "results_breadthfirst = [p.elem() for p in T.breadthfirst()]\n",
    "print(f'results_breadthfirst:{results_breadthfirst}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['(', '(', '3', '+', '2', ')', '/', '(', '5', '*', '8', ')', ')']\n"
     ]
    }
   ],
   "source": [
    "class ExpressionTree(LinkedBinaryTree):\n",
    "    #表达式树#\n",
    "    def __init__(self,token,left=None,right=None):\n",
    "        super().__init__()#继承了父类的所有属性，方法是自动继承的#\n",
    "        if not isinstance(token,str):\n",
    "            raise TypeError('token should be a string')\n",
    "        self.add_root(token)\n",
    "        if left is not None and right is not None:\n",
    "            if token not in '+-*/':\n",
    "                raise ValueError('token should be a valid operator')\n",
    "            \n",
    "            self._attach(self.root(),left,right)\n",
    "            \n",
    "    def __repr__(self):\n",
    "        pieces=[]\n",
    "        self._parenthesize_recur(self.root(),pieces)\n",
    "        return str(pieces)\n",
    "    \n",
    "    def _parenthesize_recur(self,p,result):\n",
    "        if self.is_leaf(p):#是叶子节点#\n",
    "            result.append(p.elem())\n",
    "        else:#是内部节点，递归#\n",
    "            result.append('(')\n",
    "            self._parenthesize_recur(self.left(p),result)#挂左孩子结果#\n",
    "            result.append(p.elem())\n",
    "            self._parenthesize_recur(self.right(p),result)#挂右孩子结果#\n",
    "            result.append(')')\n",
    "\n",
    "def build_expression_tree(tokens):\n",
    "        S=[]\n",
    "        for t in tokens:\n",
    "            if t in '+-*/':\n",
    "                S.append(t)\n",
    "            elif t not in '()':\n",
    "                S.append(ExpressionTree(t))\n",
    "            elif t==')':\n",
    "                right=S.pop()\n",
    "                op=S.pop()\n",
    "                left=S.pop()\n",
    "                S.append(ExpressionTree(op,left,right))\n",
    "        return S.pop()    \n",
    "    \n",
    "if __name__=='__main__':\n",
    "    tokens='((3+2)/(5*8))'\n",
    "    E=build_expression_tree(tokens)\n",
    "    print(E)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
